/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2003-2019. All rights reserved.
 ******************************************************************************************/

/*DSA*/#include "string_pm/string_pm_test.h"

//*****************************************************************************************
//    0                       bc['X']                                m-1
//    |                       |                                      |
//    ........................X***************************************
//                            .|<------------- 'X' free ------------>|
//*****************************************************************************************
int* buildBC ( char* P ) { //构造Bad Charactor Shift表：O(m + 256)
   int* bc = new int[256]; //BC表，与字符表等长
   for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化：首先假设所有字符均未在P中出现
   for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P
      bc[ P[j] ] = j; //将字符P[j]的BC项更新为j（单调递增）——画家算法
   /*DSA*/printBC ( bc );
   return bc;
}
